A standard way to approximate the distance between two vertices $p$ and $q$ in a graph is tocompute a shortest path from $p$ to $q$ that goes through one of $k$ sources, which are well-chosenvertices. Precomputing the distance between each of the $k$ sources to all vertices yields an efficient computation of approximate distances between any two vertices. One standard method for choosing $k$ sources is the so-called {\it Farthest Point Sampling} (FPS), which starts with a random vertex as the first source, and iteratively selects the farthest vertex from the already selected sources.In this paper, we analyze the stretch factor $\mathcal{F}_{\text{FPS}}$of approximate geodesics computed using FPS, which is the maximum, over all pairs of distinctvertices, of their approximated distance over their geodesic distance in the graph. We show that$\mathcal{F}_{\text{FPS}}$ can be bounded in terms of the minimal value $\mathcal{F}^\ast$ of thestretch factor obtained using an optimal placement of $k$ sources as $\mathcal{F}_{\text{FPS}}\leq 2r_e^2 \mathcal{F}^\ast+ 2 r_e^2 + 8 r_e + 1$, where $r_e$ is the length ratio oflongest edge over the shortest edge in the graph.We further show that the factor $r_e$is not an artefact of the analysis by providing a class of graphs for which$\mathcal{F}_{\text{FPS}} \geq \frac{1}{2} r_e \mathcal{F}^\ast$.

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000128 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000128 | SxmlIndent | more

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     Hal:hal-01297624
   |texte=   Analysis of Farthest Point Sampling for Approximating Geodesics in a Graph
}}